// @algorithm @lc id=279 lang=cpp 
// @title perfect-squares


// @test(12)=3
// @test(13)=2
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, 0);
        for(int i=1; i<=n; i++){
            int s = INT_MAX;
            for(int j=1; j*j<=i; j++)
                s = min(s, dp[i-j*j]);
            dp[i] = s + 1;
        }
        return dp[n];
    }
};